\hypertarget{chapter-10-pointers-to-functions}{%
\subsection{CHAPTER 10: Pointers to
Functions}\label{chapter-10-pointers-to-functions}}

Up to this point we have been discussing pointers to data objects. C
also permits the declaration of pointers to functions. Pointers to
functions have a variety of uses and some of them will be discussed
here.

Consider the following real problem. You want to write a function that
is capable of sorting virtually any collection of data that can be
stored in an array. This might be an array of strings, or integers, or
floats, or even structures. The sorting algorithm can be the same for
all. For example, it could be a simple bubble sort algorithm, or the
more complex shell or quick sort algorithm. We'll use a simple bubble
sort for demonstration purposes.

Sedgewick {[}1{]} has described the bubble sort using C code by setting
up a function which when passed a pointer to the array would sort it. If
we call that function \textbf{bubble()}, a sort program is described by
bubble\_1.c, which follows:

-----------  Program 10.1  -----------------------------------
\inputminted{c}{../src/ch10-1.c}
--------- end program 10.1 -----------------------------------

The bubble sort is one of the simpler sorts. The algorithm scans the
array from the second to the last element comparing each element with
the one which precedes it. If the one that precedes it is larger than
the current element, the two are swapped so the larger one is closer to
the end of the array. On the first pass, this results in the largest
element ending up at the end of the array. The array is now limited to
all elements except the last and the process repeated. This puts the
next largest element at a point preceding the largest element. The
process is repeated for a number of times equal to the number of
elements minus 1. The end result is a sorted array.

Here our function is designed to sort an array of integers. Thus in line
1 we are comparing integers and in lines 2 through 4 we are using
temporary integer storage to store integers. What we want to do now is
see if we can convert this code so we can use any data type, i.e. not be
restricted to integers.

At the same time we don't want to have to analyze our algorithm and the
code associated with it each time we use it. We start by removing the
comparison from within the function \textbf{bubble()} so as to make it
relatively easy to modify the comparison function without having to
re-write portions related to the actual algorithm. This results in
bubble\_2.c:

-----------  Program 10.2  -----------------------------------
\inputminted{c}{../src/ch10-2.c}
--------- end program 10.2 -----------------------------------

If our goal is to make our sort routine data type independent, one way
of doing this is to use pointers to type void to point to the data
instead of using the integer data type. As a start in that direction
let's modify a few things in the above so that pointers can be used. To
begin with, we'll stick with pointers to type integer.

-----------  Program 10.3  -----------------------------------
\inputminted{c}{../src/ch10-3.c}
--------- end program 10.3 -----------------------------------

Note the changes. We are now passing a pointer to an integer (or array
of integers) to \textbf{bubble()}. And from within bubble we are passing
pointers to the elements of the array that we want to compare to our
comparison function. And, of course we are dereferencing these pointer
in our \textbf{compare()} function in order to make the actual
comparison. Our next step will be to convert the pointers in
\textbf{bubble()} to pointers to type void so that that function will
become more type insensitive. This is shown in bubble\_4.

-----------  Program 10.4  -----------------------------------
\inputminted{c}{../src/ch10-4.c}
--------- end program 10.4 -----------------------------------

Note that, in doing this, in \textbf{compare()} we had to introduce the
casting of the void pointer types passed to the actual type being
sorted. But, as we'll see later that's okay. And since what is being
passed to \textbf{bubble()} is still a pointer to an array of integers,
we had to cast these pointers to void pointers when we passed them as
parameters in our call to \textbf{compare()}.

We now address the problem of what we pass to \textbf{bubble()}. We want
to make the first parameter of that function a void pointer also. But,
that means that within \textbf{bubble()} we need to do something about
the variable \textbf{t}, which is currently an integer. Also, where we
use \textbf{t = p{[}j-1{]};} the type of \textbf{p{[}j-1{]}} needs to be
known in order to know how many bytes to copy to the variable \textbf{t}
(or whatever we replace \textbf{t} with).

Currently, in bubble\_4.c, knowledge within \textbf{bubble()} as to the
type of the data being sorted (and hence the size of each individual
element) is obtained from the fact that the first parameter is a pointer
to type integer. If we are going to be able to use \textbf{bubble()} to
sort any type of data, we need to make that pointer a pointer to type
\textbf{void}. But, in doing so we are going to lose information
concerning the size of individual elements within the array. So, in
bubble\_5.c we will add a separate parameter to handle this size
information.

These changes, from bubble4.c to bubble5.c are, perhaps, a bit more
extensive than those we have made in the past. So, compare the two
modules carefully for differences.

-----------  Program 10.5  -----------------------------------
\inputminted{c}{../src/ch10-5.c}
--------- end program 10.5 -----------------------------------

Note that I have changed the data type of the array from \textbf{int} to
\textbf{long} to illustrate the changes needed in the \textbf{compare()}
function. Within \textbf{bubble()} I've done away with the variable
\textbf{t} (which we would have had to change from type \textbf{int} to
type \textbf{long}). I have added a buffer of size 4 unsigned
characters, which is the size needed to hold a long (this will change
again in future modifications to this code). The unsigned character
pointer \textbf{*bp} is used to point to the base of the array to be
sorted, i.e. to the first element of that array.

We also had to modify what we passed to \textbf{compare()}, and how we
do the swapping of elements that the comparison indicates need swapping.
Use of \textbf{memcpy()} and pointer notation instead of array notation
work towards this reduction in type sensitivity.

Again, making a careful comparison of bubble5.c with bubble4.c can
result in improved understanding of what is happening and why.

We move now to bubble6.c where we use the same function bubble() that we
used in bubble5.c to sort strings instead of long integers. Of course we
have to change the comparison function since the means by which strings
are compared is different from that by which long integers are compared.
And,in bubble6.c we have deleted the lines within \textbf{bubble()} that
were commented out in bubble5.c.

-----------  Program 10.6  -----------------------------------
\inputminted{c}{../src/ch10-6.c}
--------- end program 10.6 -----------------------------------

But, the fact that \textbf{bubble()} was unchanged from that used in
bubble5.c indicates that that function is capable of sorting a wide
variety of data types. What is left to do is to pass to
\textbf{bubble()} the name of the comparison function we want to use so
that it can be truly universal. Just as the name of an array is the
address of the first element of the array in the data segment, the name
of a function decays into the address of that function in the code
segment. Thus we need to use a pointer to a function. In this case the
comparison function.

Pointers to functions must match the functions pointed to in the number
and types of the parameters and the type of the return value. In our
case, we declare our function pointer as:

\begin{minted}{c}
   int (*fptr)(const void *p1, const void *p2);
\end{minted}

Note that were we to write:

\begin{minted}{c}
    int *fptr(const void *p1, const void *p2);
\end{minted}

we would have a function prototype for a function which returned a
pointer to type \textbf{int}. That is because in C the parenthesis ()
operator have a higher precedence than the pointer * operator. By
putting the parenthesis around the string (*fptr) we indicate that we
are declaring a function pointer.

We now modify our declaration of \textbf{bubble()} by adding, as its 4th
parameter, a function pointer of the proper type. It's function
prototype becomes:

\begin{minted}{c}
    void bubble(void *p, int width, int N,
                int(*fptr)(const void *, const void *));
\end{minted}

When we call the \textbf{bubble()}, we insert the name of the comparison
function that we want to use. bubble7.c illustrate how this approach
permits the use of the same \textbf{bubble()} function for sorting
different types of data.

-----------  Program 10.7  -----------------------------------
\inputminted{c}{../src/ch10-7.c}
--------- end program 10.7 -----------------------------------

References for Chapter 10:

\begin{enumerate}
\tightlist
\item
  "Algorithms in C"\\
  Robert Sedgewick\\
  Addison-Wesley\\
  ISBN 0-201-51425-7\\
\end{enumerate}

\begin{comment}
\href{epilogx.htm}{Epilog}

\href{pointers.htm}{Back to Table of Contents}
\end{comment}
